'''
Created on Oct 5, 2012

@author: Jason Huang
'''

import gmpy2
from gmpy2 import *

#Challenge #2
#def verify(N, A):
#    dif = A*A - N
#    if(dif < 0):
#        return False
#    
#    x = isqrt(dif)
#    
#    if(A+x) * (A-x) == N:
#        return A-x
#    
#    return False
#
#
#def solve():
#    N=648455842808071669662824265346772278726343720706976263060439070378797308618081116462714015276061417569195587321840254520655424906719892428844841839353281972988531310511738648965962582821502504990264452100885281673303711142296421027840289307657458645233683357077834689715838646088239640236866252211790085787877
#    Nsqrt=isqrt(N)
#    
#    for A in range(Nsqrt, Nsqrt+2**20):
#        result=verify(N,A)
#        if result != False:
#            print(result)
#            break

# Challenge 3
#def verify2(N, A2, x):
#    if (A2 - x) % 3 != 0:
#        return False
#    if (A2 + x) % 2 != 0:
#        return False
#    
#    p = (A2 - x) // 3
#    q = (A2 + x) // 2
#    
#    if p * q != N:
#       return False
#    
#    if p < q:
#        return p
#    else:
#        return q
#
#def verify1(N, A2, x):
#    if (A2 + x) % 3 != 0:
#        return False
#    if (A2 - x) % 2 != 0:
#        return False
#    
#    p = (A2 + x) // 3
#    q = (A2 - x) // 2
#    
#    if p * q != N:
#       return False
#    
#    if p < q:
#        return p
#    else:
#        return q
#
#def solve():
#    N = 720062263747350425279564435525583738338084451473999841826653057981916355690188337790423408664187663938485175264994017897083524079135686877441155132015188279331812309091996246361896836573643119174094961348524639707885238799396839230364676670221627018353299443241192173812729276147530748597302192751375739387929
#    A2 = 131459097554853198553643931189503735393893056560069574180596541504763272468756930205814940702782861638634577575123494197548004455659194920733082975077403794
#    
#    for x in range(1000000):
#        result = verify1(N, A2, x)
#        if result != False:
#            print(result)
#            break
#        result = verify2(N, A2, x)
#        if result != False:
#            print(result)
#            break

#Challenge #4
def compute_d(N, e):
    N = mpz(N)
    (_, _, d) = gcdext(N, mpz(e))
    while d < 0:
        d += N
    while d > N:
        d -= N
    return d

# a**b
def my_exp(a, b, N):
    ret = 1
    
    while b > 0:
        if b & 1 == 1:
            ret = ret * a % N
        a = a * a % N
        b = b >> 1
    return ret % N

def solve():
    N=179769313486231590772930519078902473361797697894230657273430081157732675805505620686985379449212982959585501387537164015710139858647833778606925583497541085196591615128057575940752635007475935288710823649949940771895617054361149474865046711015101563940680527540071584560878577663743040086340742855278549092581
    p=13407807929942597099574024998205846127479365820592393377723561443721764030073662768891111614362326998675040546094339320838419523375986027530441562135724301
    q=N//p
    cipher=22096451867410381776306561134883418017410069787892831071731839143676135600120538004282329650473509424343946219751512256465839967942889460764542040581564748988013734864120452325229320176487916666402997509188729971690526083222067771600019329260870009579993724077458967773697817571267229951148662959627934791540
    e=65537
    
    print("N - p * q =", N - p * q)
    
    phai = N - p - q + 1
    d = compute_d(phai, e)
    print("d * e % phai =", d * e % phai)
    
    ret = my_exp(cipher,d, N)
    
    print(hex(ret))
    
    pkcs = []
    for _ in range(256):
        c = ret & 0xFF
        if c == 0:
            break
        pkcs.append(chr(c))
        ret >>= 8
    print("".join(reversed(pkcs)))

if __name__ == '__main__':
    solve()